package jm.algorithm.recursion;

/**
 * @Description 斐波那契数列的递归
 * @date 2022/5/17 14:57
 */
public class Fibonacci {

    public static void main(String[] args) {
        System.out.println(test());
    }

    private static int test(){
        return fib3(6);
    }

    /**
     * 求第 n 项斐波那契数列
     * @param n
     * @return
     */
    private static int fib(int n){
        if (n <= 2) return 1;
        return fib(n - 1) + fib(n - 2);
    }

    /**
     * 数组优化记录
     * @param n
     * @return
     */
    private static int fibRemember(int n){
        if (n <= 2) return 1;
        // 创建一个长度为 n + 1 的数组，忽略掉索引0位置的值，直接从1开始，索引值刚好对应数列的第n项。
        int[] arr = new int[n+1];
        // 初始化前两位都是1
        arr[1] = arr[2] = 1;
        return fibR(n, arr);
    }

    private static int fibR(int n, int[] arr){
        // 如果第n项的值没有计算，就进行计算，否则直接返回。
        if (arr[n] == 0){
            arr[n] =  fibR(n - 1, arr) + fibR(n - 2, arr);
        }
        return arr[n];
    }

    /**
     * 非递归方式计算
     * @param n
     * @return
     */
    private static int fib2(int n){
        if (n <= 2) return 1;
        int[] arr = new int[n+1];
        arr[2] = arr[1] = 1;
        for (int i = 3; i <= n; i++) {
            arr[i] = arr[i -1] + arr[i - 2];
        }
        return arr[n];
     }

    /**
     * 滚动数组优化
     * @param n
     * @return
     */
    private static int fib3(int n){
        if (n <= 2) return 1;
        int[] arr = new int[2];
        arr[0] = arr[1] = 1;
        for (int i = 3; i <= n; i++) {
            arr[i % 2] = arr[(i -1) % 2] + arr[(i - 2) % 2];
        }
        return arr[n % 2];
    }

    /**
     * 位运算优化
     * @param n
     * @return
     */
    private static int fib4(int n){
        if (n <= 2) return 1;
        int[] arr = new int[2];
        arr[0] = arr[1] = 1;
        for (int i = 3; i <= n; i++) {
            arr[i & 1] = arr[(i - 1) & 1] + arr[(i - 2) & 1];
        }
        return arr[n & 1];
    }

    /**
     * 变量优化
     * @param n
     * @return
     */
    private static int fib5(int n){
        if (n <= 2) return 1;
        int first = 1;
        int second = 1;
        for (int i = 3; i <= n; i++) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

    /**
     * 特征方程优化
     * @param n
     * @return
     */
    private static int fib6(int n){
        double c = Math.sqrt(5);
        return (int) ((Math.pow((1+c) / 2, n) - Math.pow((1 - c) / 2 , n)) / c);
    }
}
